{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Алгоритмы и лямбды"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "https://en.cppreference.com/w/cpp/algorithm\n",
    "\n",
    "https://en.cppreference.com/w/cpp/numeric\n",
    "\n",
    "https://en.cppreference.com/w/cpp/language/lambda"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Примеры и философия алгоритмов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`accumulate` для знакомства"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "int sum_98(const std::vector<int>& v)\n",
    "{\n",
    "    int rv = 0;\n",
    "    for (std::vector<int>::const_iterator it = v.begin(), e = v.end(); it != e; ++it)\n",
    "        rv += *it;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "int sum_range_for_11(const std::vector<int>& v)\n",
    "{\n",
    "    int rv = 0;\n",
    "    for (int x : v)\n",
    "        rv += x;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "int sum_stl_accumulate(const std::vector<int>& v)\n",
    "{\n",
    "    // https://en.cppreference.com/w/cpp/algorithm/accumulate\n",
    "    return std::accumulate(v.begin(), v.end(), 0);\n",
    "    \n",
    "    // как это читать:\n",
    "    // std::accumulate(  // просуммировать элементы из последовательности (std::plus - дефолтная операция у accumulate)\n",
    "    //      v.begin(),   // итератор на первый элемент в последовательности\n",
    "    //      v.end(),     // итератор на следующий за последним элементом в последовательности\n",
    "    //      0);          // начальное значение суммы\n",
    "}\n",
    "\n",
    "int sum_stl_reduce(const std::vector<int>& v)\n",
    "{\n",
    "    // https://en.cppreference.com/w/cpp/algorithm/reduce (C++17)\n",
    "    return std::reduce(v.begin(), v.end());\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`count` - ещё пример"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "size_t count_range_for_11(const std::vector<int>& v, int val)\n",
    "{\n",
    "    size_t rv = 0;\n",
    "    for (auto x : v)\n",
    "        if (x == val)\n",
    "            ++rv;\n",
    "    return rv;\n",
    "}\n",
    "\n",
    "size_t count_stl(const std::vector<int>& v, int val)\n",
    "{\n",
    "    return std::count(v.begin(), v.end(), val);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`find`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "bool contains_range_for_11(const std::vector<int>& v, int val)\n",
    "{\n",
    "    for (int x : v)\n",
    "        if (x == val)\n",
    "            return true;\n",
    "    return false;\n",
    "}\n",
    "\n",
    "bool contains_stl(const std::vector<int>& v, int val)\n",
    "{\n",
    "    return std::find(v.begin(), v.end(), val) != v.end();\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "На примере `find` обсудить вопрос что лучше: наивная реализация или переиспользование алгоритма:\n",
    "* какой код чище?\n",
    "* вопрос уровня абстракции\n",
    "* оптимизации внутри алгоритмов\n",
    "* проблема читабельности алгоритмов:\n",
    "    * сколько служебных конструкций и повторений содержит элементарный код проверки, что `v` содержит `val`?\n",
    "    \n",
    "    ```c++\n",
    "    std::find(\n",
    "        current_students_in_the_class.begin(),\n",
    "        current_students_in_the_class.end(),\n",
    "        \"those little boy Einstein\")\n",
    "        != current_students_in_the_class.end();\n",
    "    ```\n",
    "    \n",
    "* ranges to the rescue! (но не совсем и с кучей оговорок)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Алгоритмы работают с итераторами!"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Класс итератора обладает некоторой гибкостью, что позволяет делать весьма заковыристые конструкции"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример**: разные варианты сортировки через один алгоритм"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// отсортируем вектор по возрастанию\n",
    "void mysort_ascending(std::vector<int>& v)\n",
    "{\n",
    "    std::sort(v.begin(), v.end());\n",
    "}\n",
    "\n",
    "// отсортируем вектор по убыванию\n",
    "void mysort_descending(std::vector<int>& v)\n",
    "{\n",
    "    std::sort(v.rbegin(), v.rend());\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример**: вывод на консоль через алгоритм (подробно объяснить пример)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "// copy - копирует последовательность\n",
    "//        https://en.cppreference.com/w/cpp/algorithm/copy\n",
    "void copy_example()\n",
    "{\n",
    "    std::vector<int> v = {1, 2, 3};\n",
    "    std::list<int> l = {4, 5, 6};\n",
    "    \n",
    "    std::copy(v.begin(), v.end(), l.begin());\n",
    "}\n",
    "\n",
    "// copy - копирует последовательность в OutputIt,\n",
    "//        но ведь можно и подшаманить OutputIt\n",
    "void print_sequence()\n",
    "{\n",
    "    std::vector<int> v = {1, 2, 3, 4, 5};\n",
    "    \n",
    "    std::copy(v.begin(), v.end(),\n",
    "              std::ostream_iterator<int>(std::cout, \" \"));\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Пример**: чтение (подробно объяснить пример)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> read_ints()\n",
    "{\n",
    "    return {\n",
    "        std::istream_iterator<int>(std::cin),\n",
    "        std::istream_iterator<int>()       \n",
    "    };\n",
    "}\n",
    "\n",
    "int sum_ints()\n",
    "{\n",
    "    std::istringstream iss(\"1 2 3 4 5\");\n",
    "    \n",
    "    return std::reduce(\n",
    "        std::istream_iterator<int>(iss),\n",
    "        std::istream_iterator<int>());\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "И в то же время гибкости класса итераторов не хватает, чтобы простые конструкции реализовывались без лишних раздумий:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void copy_example_bug()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    std::copy(a.begin(), a.end(), b.begin());\n",
    "}\n",
    "\n",
    "void copy_example_fix1()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    b.resize(a.size(), 0);\n",
    "    std::copy(a.begin(), a.end(), b.begin());\n",
    "}\n",
    "\n",
    "void copy_example_fix2()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    std::copy(a.begin(), a.end(), std::back_inserter(b));\n",
    "    // back_inserter - специальный итератор, который в operator = вызывает b.push_back(...)\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void replace_copy_bug()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    std::replace_copy(a.begin(), a.end(), b.begin(), 2, 7);\n",
    "}\n",
    "\n",
    "void replace_copy_fix()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    std::replace_copy(a.begin(), a.end(), std::back_inserter(b), 2, 7);\n",
    "}\n",
    "\n",
    "void replace_copy_better()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::vector<int> b;\n",
    "\n",
    "    b.reserve(a.size());\n",
    "    std::replace_copy(a.begin(), a.end(), std::back_inserter(b), 2, 7);\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### `std::remove` и `std::unique` - где чаще всего ошибаются"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void remove_usage_bug()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::remove(a.begin(), a.end(), 2);\n",
    "}\n",
    "\n",
    "void remove_usage_fix()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    auto new_end = std::remove(a.begin(), a.end(), 2);\n",
    "    a.resize(std::distance(a.begin(), new_end));\n",
    "}\n",
    "\n",
    "void remove_usage_fix_another_option()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    a.erase(std::remove(a.begin(), a.end(), 2),\n",
    "            a.end());\n",
    "}\n",
    "\n",
    "void remove_usage_list()\n",
    "{\n",
    "    std::list<int> l = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    l.remove(2); // list is an exception!\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void unique_usage_bug()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::sort(a.begin(), a.end());  // unique removes only adjacent uniques\n",
    "    std::unique(a.begin(), a.end());\n",
    "}\n",
    "\n",
    "void unique_usage_fix()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    std::sort(a.begin(), a.end()); // unique removes only adjacent uniques\n",
    "    auto new_end = std::unique(a.begin(), a.end());\n",
    "    a.resize(std::distance(a.begin(), new_end));\n",
    "}\n",
    "\n",
    "void unique_usage_list()\n",
    "{\n",
    "    std::list<int> l = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    l.sort();  // unique removes only adjacent uniques\n",
    "    l.unique();\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Обратить внимание на состояние контейнера после вызова remove:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void remove_result_content()\n",
    "{\n",
    "    std::vector<int> a = {1, 2, 3, 4, 5, 1, 2, 3, 4, 5};\n",
    "    auto new_end = std::remove(a.begin(), a.end(), 2);\n",
    "    \n",
    "    for (int x : a)\n",
    "        std::cout << x << \" \"; // ???\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Алгоритмы и лямбды"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`find` по условию через функцию:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "bool is_underage(const Person& p) {\n",
    "    return p.age < 18;\n",
    "}\n",
    "\n",
    "std::vector<Person> people = { ... };\n",
    "\n",
    "auto it = std::find_if(\n",
    "    people.begin(),\n",
    "    people.end(),\n",
    "    is_underage);\n",
    "\n",
    "if (it != people.end())\n",
    "    std::cout << it->age << std::endl;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`find` по условию через лямбду:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<Person> people = { ... };\n",
    "\n",
    "auto it = std::find_if(\n",
    "    people.begin(),\n",
    "    people.end(),\n",
    "    [](const Person& p){ return p.age < 18; });\n",
    "    \n",
    "if (it != people.end())\n",
    "    std::cout << it->age << std::endl;\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`count_if` - подсчёт числа элементов"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<Person> people = { ... };\n",
    "        \n",
    "const int underage_count = std::count_if(people.begin(), people.end(),\n",
    "                                         [](const Person& p){ return p.age < 18; });\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`all_of`, `any_of`, `none_of`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "auto is_underage = [](const Person& p){ return p.age < 18; };\n",
    "\n",
    "bool all_young = std::all_of(people.begin(), people.end(), is_underage);\n",
    "bool any_young = std::any_of(people.begin(), people.end(), is_underage);\n",
    "bool all_old   = std::none_of(people.begin(), people.end(), is_underage);\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`transform`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "void toupper_inplace(std::string& s)\n",
    "{\n",
    "    std::transform(\n",
    "        s.begin(), s.end(),  // input range\n",
    "        s.begin(),           // output\n",
    "        [](unsigned char c) -> unsigned char { return std::toupper(c); });  // function\n",
    "}\n",
    "\n",
    "void print_toupper(std::string& s)\n",
    "{\n",
    "    std::tranform(\n",
    "        ...  // Упражнение\n",
    "    );\n",
    "}\n",
    "\n",
    "// map-reduce example\n",
    "int sum_of_squarries(const std::vector<int>& v)\n",
    "{\n",
    "    return std::transform_reduce(\n",
    "        v.begin(), v.end(),                     // последовательность\n",
    "        0,                                      // начальный элемент в reduce-шаге (как в accumulate)\n",
    "        [](int sum, int x) { return sum + x; }, // операция reduce\n",
    "        [](int x){ return x * x; });            // операция transform\n",
    "}\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "binary search:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = { 1, 1, 2, 3, 4, 4, 4, 5, 5, 6 };\n",
    "        \n",
    "auto lower = std::lower_bound(v.begin(), v.end(), 4);\n",
    "auto upper = std::upper_bound(v.begin(), v.end(), 4);\n",
    "        \n",
    "std::copy(lower, upper,\n",
    "          std::ostream_iterator<int>(std::cout, \" \"));\n",
    "// output: 4 4 4\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "if (std::binary_search(v.begin(), v.end(), 5))\n",
    "    std::cout << \"found\";\n",
    "else\n",
    "    std::cout << \"not found\";\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`set` operations:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "**Замечание**: специфика set operations, что они работают только с отсортированными последовательностями"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v1 = {...};\n",
    "std::sort(v1.begin(), v1.end());\n",
    "        \n",
    "std::vector<int> v2 = {...};\n",
    "std::sort(v2.begin(), v2.end());\n",
    "\n",
    "// check for subset:\n",
    "if (std::includes(v1.begin(), v1.end(),\n",
    "                  v2.begin(), v2.end())) {\n",
    "    std::cout << \"v2 is subset of v1\";\n",
    "}\n",
    "\n",
    "// build union\n",
    "std::vector<int> v3 = {...};\n",
    "std::set_union(v1.begin(), v1.end(),  // отсортированная последовательность 1\n",
    "               v2.begin(), v2.end(),  // отсортированная последовательность 2\n",
    "               std::back_inserter(v3));  // куда складывать результат\n",
    "// что здесь можно было бы добавить?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "`min`/`max`"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<int> v = { ... };\n",
    "\n",
    "auto it_min = std::min_element(v.begin(), v.end());\n",
    "auto it_max = std::max_element(v.begin(), v.end());\n",
    "// почему возвращается итератор, а не сразу ссылка на минимальный элемент?\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::vector<Person> people = { ... };\n",
    "        \n",
    "auto it_min = std::min_element(people.begin(), people.end(),\n",
    "                               [](const Person& l, const Person& r) {\n",
    "                                   return l.name < r.name;\n",
    "                               });  // поиск первого по алфавиту\n",
    "\n",
    "auto it_max = std::max_element(people.begin(), people.end(),\n",
    "                               [](const Person& l, const Person& r) {\n",
    "                                   return l.age < r.age;\n",
    "                               });  // поиск самого старшего\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "etc. etc. etc."
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "##### Execution policies"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "С С++17 можно запускать некоторые алгоритмы в параллельное исполнение одним дополнительным аргументом:"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "```c++\n",
    "std::reduce(std::execution::par, v.begin(), v.end());\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "* `std::execution::seq`\n",
    "    - последовательно на одном потоке\n",
    "    - порядок обработки элементов соответствует их порядку в последовательности\n",
    "* `std::execution::par`\n",
    "    - STL вправе (но не обязана) выполнить алгоритм параллельно на нескольких потоках\n",
    "    - порядок обработки элементов на одном потоке соответствует их порядку в последовательности\n",
    "* `std::execution::unseq`\n",
    "    - последовательно на одном потоке\n",
    "    - порядок обработки элементов может не соответствовать их порядку в последовательности (например, рарешается применять векторизацию)\n",
    "* `std::execution::par_unseq`\n",
    "    - STL вправе (но не обязана) выполнить алгоритм параллельно на нескольких потоках\n",
    "    - порядок обработки элементов произвольный"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Заметки про производительность ради которой всё это затевалось:\n",
    "https://www.bfilipek.com/2018/11/parallel-alg-perf.html\n",
    "\n",
    "Спойлер: не всё так однозначно"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "<br />"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "За рамками рассказа:\n",
    "* boost algorithms\n",
    "* bit manipulations\n",
    "* math operations\n",
    "* другие реализации алгоритмов (EASTL)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.9"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
